package primary.dynamic_programming;

/**
 * @Author Elephas
 * @Date 2022/1/31
 **/
@FunctionalInterface
public interface Rob {
    int rob(int[] nums);
}
class RobImpl1 implements Rob{
    static final int[] TEST_01 = new int[]{2,7,9,3,1};
    public static void main(String[] args) {
        new RobImpl1().rob(TEST_01);
    }

    /**
     * dynamic programming, consider the transfer equation
     * f(n) = max{a[n]+f(n-2),a[n-1]+f(n-3)} , n > 3
     *      = a[0] , n = 0
     *      = max{a[0],a[1]} , n = 1
     *      = max{a[0]+a[2],a[1]}, n = 2
     * @param nums
     * @return
     */
    @Override
    public int rob(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }else if(nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        dp[2] = Math.max(dp[0] + nums[2], dp[1]);
        for (int i = 3; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 3] + nums[i - 1]);
        }
        return dp[nums.length - 1];
    }
}
